package q60_getPermutation;

import java.util.Arrays;

public class Solution_2 {
    int[] res;
    /*
    该方法则按照31题的下一个全排列
    根据当前的排列寻找下一个排列
    因此当需要寻找第k个排列时，只需要不停调用该方法即可
    仍然属于暴力搜索的范畴
     */
    public String getPermutation(int n, int k) {
        res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = i + 1;
        }

        for (int i = 1; i < k; i++) {
            nextPermutation(res);
        }

        String ans = "";
        for (int i = 0; i < res.length; i++) {
            ans += res[i];
        }

        return ans;
    }

    public void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            return;
        }

        int left = nums.length - 2;
        int right = nums.length - 1;

        while (left >= 0) {
            if(nums[left] >= nums[left + 1]){
                left--;
            }else {
                while(right > left){
                    if (nums[left] >= nums[right]) {
                        right--;
                    }else {
                        break;
                    }
                }
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                // 这里使用了冒泡排序，使后面的数组变成升序，但实际上后面的数组一定是降序排列的，是否有更快的方法直接将其变为升序
                BubbleSort(nums,left + 1);
                break;
            }
        }

        if(left == -1){
            Arrays.sort(nums);
        }

    }

    public static void BubbleSort(int[] arr,int start) {
        for (int x = start; x < arr.length - 1; x++) {
            for (int y = start; y < arr.length - 1 - x + start; y++) {
                if (arr[y] > arr[y + 1]) {
                    int temp = arr[y];
                    arr[y] = arr[y + 1];
                    arr[y + 1] = temp;
                }
            }
        }
    }
}
